package leetcode.review;

import org.junit.Test;

import java.util.Arrays;

/**
 * @author ：zsy
 * @date ：Created 2021/8/21 12:18
 * @description：
 */
public class quickSortTest {

    @Test
    public void test() {
        int[] nums = new int[]{10, 1, 2, 3, 7, 8, 9, 5, 4, 6};
        selectSort(nums);
        System.out.println(Arrays.toString(nums));
    }

    public void quick_sort(int[] nums, int left, int right) {
        if (left >= right) return;
        int l = left;
        int r = right;
        int pivot = nums[l];
        while (l < r) {
            while (l < r && nums[r] >= pivot) r--;
            nums[l] = nums[r];
            while (l < r && nums[l] <= pivot) l++;
            nums[r] = nums[l];
        }
        nums[l] = pivot;
        quick_sort(nums, left, l - 1);
        quick_sort(nums, l + 1, right);
    }

    public void headSort(int[] nums) {
        int len = nums.length;
        for (int i = len / 2 - 1; i >= 0; i--) {
            adjust(nums, i, len);
        }
        System.out.println(Arrays.toString(nums));
        for (int i = 0; i < len; i++) {
            int temp = nums[0];
            nums[0] = nums[len - 1 - i];
            nums[len - 1 - i] = temp;
            adjust(nums, 0, len - 1 - i);
        }
    }

    public void adjust(int[] nums, int parentIndex, int len) {
        int temp = nums[parentIndex];
        int childIndex = parentIndex * 2 + 1;
        while (childIndex < len) {
            if (childIndex + 1 < len && nums[childIndex + 1] > nums[childIndex]) childIndex++;
            if (nums[childIndex] <= temp) break;
            nums[parentIndex] = nums[childIndex];
            parentIndex = childIndex;
            childIndex = childIndex * 2 + 1;
        }
        nums[parentIndex] = temp;
    }

    public void bubbleSort(int[] nums) {

        for (int i = 0; i < nums.length - 1; i++) {
            boolean isChange = false;
            for (int j = 0; j < nums.length - i - 1; j++) {
                if (nums[j] > nums[j + 1]) {
                    isChange = true;
                    int tmp = nums[j];
                    nums[j] = nums[j + 1];
                    nums[j + 1] = tmp;
                }
            }
            if (!isChange)
                break;
        }
    }

    public void selectSort(int[] nums) {
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < len; j++) {
                if (nums[j] < nums[minIndex]) {
                    minIndex = j;
                }
            }
            int tmp = nums[minIndex];
            nums[minIndex] = nums[i];
            nums[i] = tmp;
        }
    }
}
